package a_doubleWrite;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 有重复元素
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 注意：解集不能包含重复的组合。 

 * @author: luolidong
 * @create: 2021-07-18 10:45
 * @version: 1.0
 */
public class L40 {
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrack(candidates, target, 0, new ArrayList<>());
        return list;
    }
    public void backTrack(int[] candidates, int target,int index,List<Integer> clist){
        if(target<0||index>=candidates.length) return;
        if(target==0){
            list.add(new ArrayList<>(clist));
        }
        for (int i = index; i <candidates.length ; i++) {
            if(i>index&&candidates[i]==candidates[index]) continue;
            target-=candidates[i];
            clist.add(candidates[i]);
            backTrack(candidates, target, i+1, clist);
            clist.remove(clist.size()-1);
            target+=candidates[i];
        }
    }
}
